<?php
/**
 * @title 134. 加油站 - 到达各个加油站的油量比较
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $gas
     * @param Integer[] $cost
     * @return Integer
     */
    function canCompleteCircuit($gas, $cost) {
        /**
         * @since 2020-07-31 确保有解
         */
        if(array_sum($gas) < array_sum($cost)){
            return -1;
        } else {}

        /**
         * @since 2020-07-31 长度
         */
        $len = count($gas);

        /**
         * @since 2020-08-03 到各个点最大油量
         */
        $maxGas = 0;

        /**
         * @since 2020-08-03 终点到起点的剩余油量
         */
        if($gas[$len-1] >= $cost[$len-1]){
            $maxGas = $gas[$len-1] - $cost[$len-1];
            $s = $len-1;
        } else {
            $maxGas = 0;
            $s = -1;
        }

        /**
         * @since 2020-08-03 遍历每个加油站
         */
        for($i=0; $i<$len; $i++){
            // echo "i={$i}, maxGas={$maxGas}, s={$s}, ";

            /**
             * @since 2020-08-03 上一站到到本站如果油量非空, 加油后油量比直接比从这个加油站出发更多
             */
            if($maxGas == 0){
                $maxGas = $gas[$i];
                $s = $i;
            } else {
                $maxGas += $gas[$i];
            }

            /**
             * @since 2020-08-03 是否足够去下一个油站
             */
            if($maxGas >= $cost[$i]){
                $maxGas = $maxGas-$cost[$i];
            } else {
                $maxGas = 0;
                $s = -1;
            }

            // echo "nextGas={$maxGas}, nextS={$s}", PHP_EOL;
        }

        /**
         * @return
         */
        return $s;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.31_4.php
 */
$datas = [
    [[3,1,1],[1,2,2]],
    // [[1,2,3,4,5],[3,4,5,1,2]],
    // [[2,3,4],[3,4,3]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->canCompleteCircuit($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
